import java.util.*;

/**
 * @author hewei
 * @version 1.0
 * @description: 2008. 出租车的最大盈利
 * @date 2022/11/8 15:00
 */

public class MaxTaxiEarnings {

    public long maxTaxiEarnings1(int n, int[][] rides) {
        int m = rides.length;
        long[] dp = new long[n + 1];
        HashMap<Integer, List<Integer>> map = new HashMap<>();
        for (int i = 0; i < m; i++) {
            int[] ride = rides[i];
            if (!map.containsKey(ride[0])) map.put(ride[0], new ArrayList<>());
            map.get(ride[0]).add(i);
        }
        for (int i = n; i >= 1; i--) {
            List<Integer> list = map.get(i);
            dp[i] = i == n ? 0 : dp[i + 1];
            if (list != null) {
                for (Integer temp : list) {
                    int[] ride = rides[temp];
                    dp[i] = Math.max(dp[i], ride[1] - ride[0] + ride[2] + dp[ride[1]]);
                }
            }
        }
        return dp[1];
    }

    public long maxTaxiEarnings(int n, int[][] rides) {
        int m = rides.length;
        int[][] jobs = new int[m + 1][3];
        for (int i = 0; i < m; i++) {
            jobs[i] = new int[]{rides[i][0], rides[i][1], rides[i][2] + rides[i][1] - rides[i][0]};
        }
        jobs[m] = new int[]{Integer.MAX_VALUE, 0, 0};
        Arrays.sort(jobs, Comparator.comparingInt(a -> a[0]));
        long[] dp = new long[m + 1];
        for (int i = m - 1; i >= 0; i--) {
            dp[i] = dp[i + 1];
            int l = i + 1, r = m;
            while (l < r) {
                int mid = (r - l) / 2 + l;
                if (jobs[mid][0] >= jobs[i][1]) {
                    r = mid;
                } else {
                    l = mid + 1;
                }
            }
            dp[i] = Math.max(dp[i], dp[l] + jobs[i][2]);
        }
        return dp[0];
    }
}
